package leetcode;

public class TrappingRainWater {

    public static void main(String[] args) {
        TrappingRainWater trappingRainWater = new TrappingRainWater();
        System.out.println(trappingRainWater.trap(new int[]{0,1,0,2,1,0,1,3,2,1,2,1}));
    }

    public int trap(int[] height) {
        int n = height.length;
        if(n == 0) return 0;
        int sum = 0;
        // 从左到右找到每个元素最高的值
        // 从右到左找到每个元素最高的值
        // 动态规划：某个元素的两侧最矮的值就是高度，减去元素的大小就是存水量
        int leftMax [] = new int[n];
        leftMax [0] = height[0];
        for (int i = 1; i < n; ++i) {
            leftMax [i] = Math.max(leftMax [i - 1], height [i]);
        }

        int rightMax [] = new int[n];
        rightMax [n - 1] = height[ n - 1 ];
        for (int i = n - 2; i >= 0; --i) {
            rightMax [i] = Math.max(rightMax [i + 1], height [i]);
        }

        for (int i = 0; i < n; ++i) {
            sum += Math.min(leftMax [i], rightMax [i]) - height[i];
        }
        return sum;
    }


}
